/**
 * FileName: L41
 * Author:   powersi
 * Date:     2021/3/3 17:20
 * Description:
 */
package com.zm.demo.core.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * Description: 
 * Author:      powersi
 * Date:        2021/3/3 17:20
 */
public class L41 {

    public int firstMissingPositive(int[] nums) {

        //正数：[1,n]
        //下标：[0,n-1]
        int length = nums.length;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >=1 && nums[i] <= length){
                int temp = nums[i];
                nums[i] = nums[temp-1];
                nums[temp-1] = temp;
            }

        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != (i+1)){
                return i+1;
            }
        }
        return length + 1;
    }

    public int firstMissingPositive1(int[] nums) {
        int max = Integer.MIN_VALUE;
        Map<Integer,Integer> map = new HashMap<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
            if (nums[i]>0){
                map.put(nums[i],nums[i]);
            }
        }

        for (int i = 1; i < max; i++) {
            if (map.get(i) == null){
                return i;
            }
        }
        return max+1;
    }
}
